/**
 * @author: sundx
 * @date: 2020-06-10 14:17:46
 * @Last Modified by: sundx
 * @Last Modified time: 2020-06-10 14:28:40
 */
#ifndef __SORT_H__
#define __SORT_H__
#include <algorithm>

//  选择排序，时间 O(n^2)， 空间O(n);
template <typename T> void selectionSort(T arr[], int n) {
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (arr[i] > arr[j]) {
        std::swap(arr[i], arr[j]);
      }
    }
  }
}

/*                       插入排序                         */

// 插入排序  时间 O(n^2)， 空间O(n);
template <typename T> void insertionSort(T arr[], int n) {
  for (int i = 1; i < n; ++i) {   //寻找元素arr[ℹ]合适的插入位置；
    for (int j = i; 0 < j; --j) { // j表示元素当前所到的位置
      if (arr[j] < arr[j - 1]) {
        std::swap(arr[j], arr[j - 1]);
      } else { //认为已经到了一个合适的位置；
        break;
      }
    }
  }
}

// 优化后，减少了交换次数，每次只交换一次；
template <typename T> void insertionSort2(T arr[], int n) {
  for (int i = 1; i < n; ++i) { //寻找元素arr[ℹ]合适的插入位置；
    T e = arr[i];
    int j;
    for (j = i; 0 < j; --j) { // j表示元素当前所到的位置
      if (e < arr[j - 1]) {
        arr[j] = arr[j - 1]; //将前一个元素替代当前元素
      } else {               //认为已经到了一个合适的位置；
        break;
      }
    } // 跳出循环的时候，j的位置就是a[i]应该插入的位置；
    arr[j] = e;
  }
}

// 插入排序，从[l,r];
template <typename T> void insertionSort3(T arr[], int l, int r) {
  for (int i = l + 1; i <= r; ++i) {
    T e = arr[i];
    int j;
    for (j = i; j > l; --j) {
      //   if (arr[j - 1] > arr[j]) {   //注意这里的错误；
      if (arr[j - 1] > e) {
        arr[j] = arr[j - 1];
      } else {
        break;
      }
    }
    arr[j] = e;
  }
}

/*                       归并排序                         */

// 将[l,mid],[mid+1,r]两个已经排序好的数组进行合并；
template <typename T> void __merge(T arr[], int l, int r) {
  int i = l, j = (l + r) / 2 + 1, k = 0;
  int mid = (l + r) / 2;
  T temp[r - l + 1];
  for (k = 0; k < r - l + 1; ++k) { //复制；
    temp[k] = arr[l + k];
  }
  for (k = l; k <= r; ++k) { // k是从l开始，到r
    if (i > mid) {
      arr[k] = temp[j - l]; // 有一个l的偏移；
      ++j;
    } else if (j > r) {
      arr[k] = temp[i - l];
      ++i;
    } else if (temp[i - l] < temp[j - l]) {
      arr[k] = temp[i - l];
      ++i;
    } else {
      arr[k] = temp[j - l];
      ++j;
    }
  }
}

// 对[l，r]闭区间内元素进行归并排序
template <typename T> void __mergeSort(T arr[], int l, int r) {
  //   if (l >= r) {
  //     return;
  //   }
  if (r - l <= 15) {
    insertionSort3(arr, l, r);
    return;
  } else {
    int mid = (l + r) / 2; // TODO:这里l和r特别大的时候会有越界风险；
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid + 1, r);
    if (arr[mid] > arr[mid + 1]) // 这种情况下才需要进行merge；
      __merge(arr, l, r);
  }
}

// 归并排序 O(NlogN) 空间O(N)
template <typename T> void mergeSort(T arr[], int n) {
  __mergeSort(arr, 0, n - 1); //调用子函数；
}

//__merge()重载；
// [l,mid-1],[mid,r]
template <typename T> void __merge(T arr[], int l, int mid, int r) {
  T temp[r - l + 1];
  int i = l, j = mid, k = 0;
  for (k = 0; k < r - l + 1; ++k) {
    temp[k] = arr[l + k];
  }
  for (k = l; k <= r; ++k) {
    if (i == mid) { //左边越界，右边直接拷贝
      arr[k] = temp[j - l];
      ++j;
    } else if (j > r) {
      arr[k] = temp[i - l];
      ++i;
    } else if (temp[i - l] < temp[j - l]) {
      arr[k] = temp[i - l];
      ++i;
    } else {
      arr[k] = temp[j - l];
      ++j;
    }
  }
  return;
}

//自底而上，迭代；
template <typename T> void mergeSortBU(T arr[], int n) {
  //第一大轮循环中，第一次看1个元素，第二次2个，第三次4个...
  for (int i = 0; i < n; i += 16) {
    insertionSort3(arr, i, std::min(i + 15, n - 1));
  }

  for (int sz = 16; sz <= n; sz += sz) {
    for (int window = 0; window + sz < n; window += sz + sz) {
      // 每次对2个sz大小的元素进行归并；
      //[window，window+sz-1] [window+sz，window+sz +sz-1]  下标；
      if (arr[window + sz] >= arr[window + sz - 1]) {
        continue;
      }
      __merge(arr, window, window + sz, std::min(window + sz + sz - 1, n - 1));
    }
  }
}

/*                       快速排序                         */

// 第一版！！！！！！！！！！！！
// 返回值为p，使得arr[l...p-1]<arr[p]<arr[p+1...r];
template <typename T> int __partition1(T arr[], int l, int r) {
  std::swap(arr[rand() % (r - l + 1) + l], arr[l]);
  T e = arr[l];
  // arr[l...p-1]<arr[p]<arr[p+1...i);
  int p = l; //初始位置，p取l，对于左边，是一个不存在区间，为空；
  // 对于右边因为i从l+1 开始，所以也是空；   难点～～
  for (int i = l + 1; i <= r; ++i) {
    //加入i所在位置的元素比e小，那么需要交换第一个大于e的元素，也就是p+1；
    if (arr[i] < e) {
      std::swap(arr[p + 1], arr[i]);
      ++p;
    }
  }
  std::swap(arr[l], arr[p]);
  return p;
}

template <typename T> void __quickSort1(T arr[], int l, int r) {
  if (l >= r)
    return;
  int p = __partition1(arr, l, r);
  __quickSort1(arr, l, p - 1);
  __quickSort1(arr, p + 1, r);
}

template <typename T> void quickSort1(T arr[], int n) {
  srand(time(NULL));
  __quickSort1(arr, 0, n - 1);
}

// 第二版！！！！！！！！！！！！！
template <typename T> int __partition2(T arr[], int l, int r) {
  std::swap(arr[rand() % (r - l + 1) + l], arr[l]);
  T e = arr[l];
  // arr[l+1,i) < e && e < arr(j,r]
  // 为了保证区间初始状态为空，i取l+1，j取r；
  int i = l + 1, j = r;
  while (true) {
    while (i <= r && arr[i] < e) {
      ++i;
    }
    while (j >= l + 1 && arr[j] > e) {
      --j;
    }
    if (i > j)
      break;
    std::swap(arr[i], arr[j]);
    ++i;
    --j;
  }
  //退出循环时，arr[j]所在的位置为从后往前，第一个 <=e的，(整个数组最后一个；
  // i所在从前往后，第一个大于等于 e的位置；
  std::swap(arr[l], arr[j]);
  return j;
}

template <typename T> void __quickSort2(T arr[], int l, int r) {
  //   if (l >= r)
  //     return;
  if (r - l <= 15) {
    insertionSort3(arr, l, r); //插入排序；
    return;
  }

  int p = __partition2(arr, l, r);
  __quickSort2(arr, l, p - 1);
  __quickSort2(arr, p + 1, r);
}
template <typename T> void quickSort2(T arr[], int n) {
  srand(time(NULL));
  __quickSort2(arr, 0, n - 1);
}

// 迷！！！！！！！！！！！！！！
template <typename T> int __partition3(T arr[], int l, int r) {
  std::swap(arr[rand() % (r - l + 1) + l], arr[l]);
  T e = arr[l];
  int i = l;
  int j = r;
  while (i != j) {
    while (arr[j] >= e && i < j) { //从右边找到一个比e小的数字
      --j;
    }
    while (arr[i] <= e && i < j) { //从左边找到一个比e大的数字
      ++i;
    }
    if (i < j) {
      //两个数字还未碰上时，交换他们；
      std::swap(arr[i], arr[j]);
    }
  }

  //循环跳出条件为，从后往前找到了一个比e小的数字，且j=i，也就是恰好是i所在的数字；
  std::swap(arr[l], arr[i]);
  return i;
}

// 第一版！！！！！！！！！！！！
template <typename T> void __quickSort3(T arr[], int l, int r) {

  //   if (l >= r)
  //     return;
  if (r - l <= 15) {
    insertionSort3(arr, l, r);
    return;
  }

  int p = __partition3(arr, l, r);
  __quickSort3(arr, l, p - 1);
  __quickSort3(arr, p + 1, r);
}
template <typename T> void quickSort3(T arr[], int n) {
  srand(time(NULL));
  __quickSort3(arr, 0, n - 1);
}

#endif